package com.lwt.codetop.linkedLists;

// 92. 反转链表 II

/**
 * 翻转 left~right的链表
 * 思路：首先要找到翻转区间的前驱，即移动left - 1次
 *      然后翻转 right - left次
 *      最后更新指针的指向
 */
public class ReverseLinkedListII {
    public static void main(String[] args) {
        // 构建测试用例
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        int left = 3, right = 5;
        // 翻转链表
        ListNode res = reverseBetween(head, left, right);
        while(res != null){
            System.out.print(res.val + " ");
            res = res.next;
        }
    }

    /**
     * 翻转left~right部分的链表
     * @param head
     * @param left
     * @param right
     * @return
     */
    private static ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        // 找到翻转区域的前驱
        for (int i = 0; i < left - 1; i++) {
            p = p.next;
        }
        // 翻转left~right
        ListNode a = p.next, b = a.next;
        for (int i = 0; i < right - left; i++) {
            ListNode c = b.next;
            b.next = a;
            a = b;
            b = c;
        }
        // 改变指针指向
        ListNode t = p.next;
        p.next = a;
        t.next = b;

        return dummy.next;
    }
}
